'''
法一：
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums1 = sorted(nums)
        return nums1[len(nums1) - k]
'''
# 法二 快排
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums, k):
            pivot = random.choice(nums)
            big, equal, small = [], [],[]
            for num in nums:
                if num > pivot:
                    big.append(num)
                elif num < pivot:
                    small.append(num)
                else:
                    equal.append(num)
            if k <= len(big):
                # 第 k 大元素在 big 中，递归划分
                return quick_select(big, k)
            if len(nums) - len(small) < k:
                # 第 k 大元素在 small 中，递归划分
                return quick_select(small, k - len(nums) + len(small))
            return pivot
        return quick_select(nums, k)